package BasicMath;

import java.io.*;
import java.lang.System;
import java.util.List;

public class EuclidGCD {
	public final static int choice = 2;
	
	//O(n) at worst case.  For example GCD of 1000 and 1 will be 1, but this will take 999 steps to get there (num1 - num2).
	public static int TwoSubtractFindGCD(int a, int b)
	{
		if (a == 1 || b ==1)
			return 1;
		while (a != b)
		{
			if (a>b)
				a = a-b;
			else
				b = b-a;
		}
		return a;
	}
	
	public static int MultipleSubtractFindGCD(List<Integer> list)
	{
		Integer values[] = new Integer[list.size()];
		values = list.toArray(values);
		for (int i=0; i<values.length-1; i++)
			values[i+1] = TwoSubtractFindGCD(values[i], values[i+1]);
		
		return values[values.length-1];
	}
	
	//"Never requires more division steps than five times the number of digits of the smaller integer" -- wikipedia:Euclidean algorithm
	public static int TwoRemainderFindGCD(int a, int b)
	{
		while (a != 0 && b != 0)
		{
			if (a>b)
				a = a%b;
			else
				b = b%a;
		}
		
		return (a>b)?a:b;
	}
	
	public static int MultipleRemainderFindGCD(List<Integer> list)
	{
		Integer values[] = new Integer[list.size()];
		values = list.toArray(values);
		for (int i =0; i<values.length-1; i++)
			values[i+1] = TwoRemainderFindGCD(values[i], values[i+1]);
		
		return values[values.length-1];
	}
	
	public static int UserEnterNumber()
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = "";
		Integer value = -1;
		try
		{
			input = br.readLine();
			value = Integer.parseInt(input);
			
		}
		catch (Exception e)
		{
			System.out.println("IO Error");
			System.out.println(e.getMessage());
			System.exit(-1);
		}
		
		return value;
	}
}
